Skip to main content

Public key and Pre knowledge

信安数学爷们可以跳过这章.

Math​

Integers mod N​

gcd，以及ξ(N)\xi(N)(欧拉函数)。

关于欧拉函数，可以看 OI-WIKI

需要了解其积性函数的性质。

Division Remainder Module​

数论基础的mod表示：a≡b mod Na \equiv b~ mod~ N 其性质较为简单。

Groups​

近世代数研究的是抽象意义上的代数运算，因此其运算规则需要重新定义。群这种代数结构满足以下性质：

  1. 闭包：∀g,h∈G,g⋅h∈G\forall g,h\in G,g\cdot h\in G.
  2. 单位元：∃e∈G s.t.∀g∈G,e⋅g=g=g⋅e\exists e\in G~ s.t. \forall g\in G,e\cdot g=g=g\cdot e.
  3. 逆元：∀g∈G,∃h∈G,g⋅h=e=h⋅g\forall g\in G,\exists h\in G,g\cdot h=e=h\cdot g
  4. 结合律：∀g,h,f∈G,(g⋅h)⋅f=g⋅(h⋅f)\forall g,h,f\in G,(g\cdot h)\cdot f=g\cdot (h\cdot f)

群满足以下性质被称为交换群：

∀g,h∈G,g⋅h=h⋅g\forall g,h\in G,g\cdot h=h\cdot g 在密码学中，我们基本上只讨论交换群。

Example:

若N>0，那么G={a⋅bmodN}G=\{a\cdot b mod N\}是一个群。

幂​

简写gm=g⋅g⋅g...gg^m=g\cdot g\cdot g...g,加法群也是类似定义，于是有：

  1. gi+j=gi⋅gjg^{i+j}=g^i\cdot g^j
  2. gij=(gi)j=(gj)ig^{ij}=(g^i)^j=(g^j)^i
  3. g−i=(gi)−1=(g−1)ig^{-i}=(g^i)^{-1}=(g^{-1})^i

order of a Group​

若GG是有限群，那么m=∣G∣m=|G|为其阶。 则满足以下性质：∀g∈G,gm=1\forall g\in G,g^m=1（单位元） 推论：GG为有限群，那么gx=gx mod mg^x=g^{x~ mod~ m}

求幂方式​

对于求ana^n中n十分庞大的情况，可以通过快速幂的思想快速求解。关于快速幂，同样可以查询OIWIKI。

Cyclic Groups​

现定义G={g0,g1,...}G=\{g_0,g_1,...\}为有限群，其阶为m。

设i≤mi\leq m是能够满足以下性质的最小正整数：gi=1g^i=1,其可以构建这样一个群：gi=g0,gi+1=gi,<g>={g0,g1,...gi−1}g^i=g^0,g^{i+1}=g^i,< g >=\{g^0,g^1,...g^{i-1}\}

那么，我们叫ii为元素gg的阶，而<g>< g >是GG的子群，由gg生成。

若由一个元素g∈Gg\in G,其阶为m=∣G∣m=|G|，那么G被称为循环群。

info

若GG为mm阶群，g∈Gg\in G有阶ii ，则i∣mi|m

若pp是素数，则Zp∗={1,2,3,4,...p−1}Z^*_{p}=\{1,2,3,4,...p-1\}是阶为p−1p-1的循环群。

Generating random primes​

Bertrand’s postulate

∀n>1\forall n>1,the fraction of n-bit integers that are prime is at least 1/3n1/3n.

有算法能够生成随机的素数，但实现其算法的要点在于如何判断一个数为素数。于是有素性测试。

Probabilistic primality test（素性测试）​

确定性的测试一个素数思路很简单，但用概率测试能够更有效率的解决。其对于所有的素数，都会输出正确的结果，但可能会误判合数为素数。

素性测试采用 费马小定理，而素性测试可以见 这里

因数​

对于一个数而言，若其只有大的质因数，那么分解它是很难的；但找到任意给定的N的较小因数是较为简单的：Pollard rhoPollard~rho算法。关于Pollard rho算法，可以在OI WIKI中找到。

定义GenModule实验：

事先给定安全参数n

  1. 预言机生成（N,p,qN,p,q），返回敌手NN，其中N=pqN=pq，pqpq为nbits 素数.
  2. 敌手发送p′,q′p',q'，若N=p′q′N=p'q'，返回1，否则返回0.
Factoring hard

Factoring is hard 这一结论基于以下性质：对任意PPT 敌手 Pr[FactoringA,GenModulus=1]≤negl(n)Pr[Factoring_{\mathcal{A,\mathbf{GenModulus}}}=1]\leq negl(n)

RSA assumption​

定义GenRSA实验：

事先给定安全参数n。

  1. 预言机生成（N,e,dN,e,d）返回敌手N,e,yN,e,y，其中N=pq,gcd(e,ϕ(N))=1,ed=1 modϕ(N)N=pq,gcd(e,\phi(N))=1,ed=1~ mod \phi(N),y为均匀选择。
  2. 敌手返回x，若xe=y modNx^e=y~ mod N 返回1，否则返回0.

定义RSA是困难的，类似上方Factoring 定义方式。

RSA的经典构造方式，就不用细讲了罢）网上一搜都有的。

需要说明的是，RSA算法基于的假设并不是“大整数因式分解是困难的”，其基于的是上方的RSA问题。即使现基于RSA的攻击基本上都是基于大整数因式分解。

实际上，RSA的难度不可能比Factoring更难，但RSA问题的难易程度是否由Factoring所决定，也是一个悬而未决的问题。一般而言，RSA问题可能可以在PPT内完成，但Factoring则不能。

同时，普通教材上的RSA实际上不太可能在实际方案中出现，实际方案的RSA已经经过修改，但仍基于最基本的RSA算法。

Generators​

info

若G为q阶循环群，q>1,其生成元为g，那么G一共有ϕ(q)\phi(q)个生成元。

推论：若G为q阶群，q为素数，那么G为循环群；同时，除了单位元，任何G的元素都是生成元。

若G为q阶群，q可以表示为 ∏piei\prod p_i^{e_i}，则选择qi=q/piq_i=q/p_i，当且仅当h∈G,hqi≠1h\in G,h^{q_i}\neq 1时h为G的生成元。

Discrete logarithms​

现选择q阶循环群，那么可以定义DL problem：

DL problem：给定h=gxh=g^x去寻找x。

让G\mathcal{G}为群生成器，其输入为1n1^n,输出一个循环群 (G,q,g)(G,q,g),其中∣q∣=n|q|=n。

则有：DLOGA,GDLOG_{\mathcal{A},\mathcal{G}}:

  1. 运行 G(1n)\mathcal{G}(1^n).
  2. 均匀选择元素h∈Gh\in G
  3. 敌手被给定：G,q,g,hG,q,g,h并返回预言机x∈Zqx\in \mathbb{Z}_q
  4. 若gx=hg^x=h输出1，否则返回0。

warning Discrete-logarithm 定义离散对数问题是难的，其依赖于上述实验对任意PPT敌手： Pr[DLOGA,G=1]≤negl(n)Pr[DLOG_{\mathcal{A},\mathcal{G}}=1]\leq negl(n) :::

基于DL problem，现讨论以下较弱的问题

computational Diffie-Hellman(CDH)​

让DHg(h1,h2)=glogg(h1)⋅logg(h2)DH_g(h_1,h_2)=g^{log_g(h_1)\cdot log_g(h_2)} 若h1=gx1,h2=gx2h_1=g^{x_1},h_2=g^{x_2},那么DHg(h1,h2)=gx1x2=h1x2=h2x1DH_g(h_1,h_2)=g^{x_1x_2}=h_1^{x_2}=h_2^{x_1}

CDH problem: Given G,q,g,h1,h2G,q,g,h_1,h_2，计算 DHg(h1,h2)DH_g(h_1,h_2)

其概率定义类似上节。

Decision Diffie-Hellman(DDH)​

给定(G,q,g)(G,q,g)并均匀随机选择h1,h2∈Gh_1,h_2\in G区分DHg(h1,h2)DH_g(h_1,h_2)的结果和随机选择的元素h′∈Gh'\in G、

其类似的定义也是上方的概率定义。

conclusion​

若能解决DH问题，自然也能解决DDH和CDH问题，DDH是比CDH更强的假设；但也有groups满足CDH更难，DDH是简单的性质。

在实际问题中，由于素数阶的群生成元更容易找到，且DL Problem的强度是最高的，同时还有其他的性质（这里不讨论），一般而言选择素数阶的群。

Elliptic curves(椭圆曲线)​

这里要引入域的概念。关于域，一般而言是满足两类运算的代数结构，具体可见OI WIKI。

在密码学中，为了让DLP更难，需要选择大素数阶的群（子群）。而对于椭圆曲线群的阶，则有以下讨论：

定义二次剩余(quadratic residue,QR),选择y∈Zpy\in \mathbb{Z}_p，其为模p的二次剩余时，满足：∃x∈Zp,x2=y modp\exists x\in \mathbb{Z}_p,x^2=y~ mod p.

对于大于2的素数p。有一半的Zp\mathbb{Z}_p,且每个QR都有两个square roots。

剩下的真看不懂了，似乎是构造了一个素数等式，若满足有该素数表达式的点，则有p+1个 point of infinite？而这个等式似乎和构造二次剩余的交点个数有关？

直接上结论了。

Hasse bound

p为素数，E为Zp\mathbb{Z}_p的椭圆曲线，则有： p+1−2p≤∣E(Zp)∣≤p+1+2pp+1-2\sqrt{p}\leq |E(\mathbb{Z}_p)|\leq p+1+2\sqrt{p}

选择椭圆曲线是，一般而言是随机选择，其便可以极其接近“均匀”分布在Hasse bound所确定的区间。需要注意的是要排除弱椭圆曲线。

通过椭圆曲线，还可以定义椭圆曲线上的DLP(ECDLP)，相对应的也可以定义CDH,DDH。

Application​

觉得很重要，说明了一些有关椭圆曲线的攻击、后门，以及新型应用，但不想翻译，直接贴原文了。

Although curves standardized decades ago are still widely used, there happened a lot in the last decades. Starting with Kocher’99, side-channel attacks and their couter-measures have become extremely sophisticated. Decades of new research yielding faster, simpler and safer ways to do ECC. Suspicion surrounding previous standards: snowden leaks, dual EC-DRBG backdoor, etc., lead to conjectured.weaknesses in the NIST curves. Other specific classes of curves enable secure cryptographic pairings. And thus interesting applications such as practical identity-and attribute-based cryptography.

基于椭圆曲线的双线性映射，这里略。

碎碎念​

笑死，原PPT这里是极短的，老师似乎两节课就结束了，但要理解这些概念对于初学者而言还是不太够。只能看之后自己能不能补上了。